public class Solution37 {
    boolean slove = false;
    int[][] rows = new int[9][9], columns = new int[9][9], subBoxes = new int[9][9];

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    rows[i][num]++;
                    columns[j][num]++;
                    int index = (i / 3) * 3 + j / 3;
                    subBoxes[index][num]++;
                }
            }
        }
        dfs(board, 0, 0);
    }

    private void dfs(char[][] board, int row, int col) {
        for (int i = row; i < 9; i++) {
            for (int j = col; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; k++) {
                        if (rows[i][k] == 0 && columns[j][k] == 0 && subBoxes[(i / 3) * 3 + j / 3][k] == 0) {
                            board[i][j] = (char) (k + '1');
                            rows[i][k]++;
                            columns[j][k]++;
                            subBoxes[(i / 3) * 3 + j / 3][k]++;
                            dfs(board, i, j);
                            if (slove)
                                return;
                            rows[i][k]--;
                            columns[j][k]--;
                            subBoxes[(i / 3) * 3 + j / 3][k]--;
                        }
                    }
                    board[i][j] = '.';
                    return;
                }
            }
            col = 0;
        }
        System.out.println(board[8][5]);
        slove = true;
    }
/*
    public void solveSudoku(char[][] board) {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; k++) {
                        if (!slove) {
                            board[i][j] = (char) (k + '1');
                            if (isValidSudoku(board)) {
                                solveSudoku(board);
                                if (slove)
                                    return;
                            }
                        }
                    }
                    board[i][j] = '.';
                    return;
                }

            }

        }
        slove = true;
    }

    private boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9], columns = new int[9][9], subBoxes = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    rows[i][num]++;
                    columns[j][num]++;
                    int index = (i / 3) * 3 + j / 3;
                    subBoxes[index][num]++;
                    if (rows[i][num] > 1 || columns[j][num] > 1 || subBoxes[index][num] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }*/

}
